package Demo47;

import java.util.Random;


/**
 * 数组中的第k个最大的元素
 * https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
 */
class Solution {
    public int findKthLargest(int[] nums, int k) {
        return func(nums,0,nums.length - 1 ,k);
    }

    private int func(int[] nums, int begin, int end, int k) {
        if(begin == end) return nums[begin];
        int left = begin - 1,right = end + 1;
        int key = nums[new Random().nextInt((end - begin + 1) + begin)];
        for(int i = begin; i < right;i++) {
            if(nums[i] < key) {
                left++;
                swap(nums,i,left);
            }else if(nums[i] > key) {
                right --;
                swap(nums,i,right);
                i--;
            }
        }
        int c = end - right + 1,b = right - left - 1;
        if(c>=k) {
            return func(nums,right,end,k);
        }else if((c + b) >= k) {
            return key;
        }else {
            return func(nums,begin,left,k - c - b);
        }
    }

    private void swap(int[] nums, int i, int right) {
        int tmp = nums[i];
        nums[i] = nums[right];
        nums[right] = tmp;
    }
}